package Array;

import java.util.*;

public class RandomizedSet {

    private List<Integer> list;

    private Map<Integer, Integer> indexMap;
    /** Initialize your data structure here. */
    public RandomizedSet() {
        list = new ArrayList<>();
        indexMap = new HashMap<>();
    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if(indexMap.get(val) != null) {
            return false;
        }
        list.add(val);
        indexMap.put(val,list.size()-1);
        return true;
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if(indexMap.get(val) == null) {
            return false;
        }
        swapIndex(val);
        list.remove(list.size()-1);
        return true;
    }

    private void swapIndex(int val) {
        int indexA = indexMap.get(val);
        int temp = list.get(list.size()-1);
        list.set(indexA, temp);
        indexMap.put(temp,indexA);
        indexMap.remove(val);
    }

    /** Get a random element from the set. */
    public int getRandom() {
        Random random = new Random();
        return list.get(random.nextInt(list.size()));
    }

    public static void main(String[] args) {
        RandomizedSet r = new RandomizedSet();
        for (int i = 0; i < 10; i++) {
            r.insert(i);
        }
        System.out.println(r.getRandom());
        r.remove(5);
        System.out.println(r.getRandom());
    }
}
